package 链表;

public class 复制带随机指针的链表 {
    public static void main(String[] args) {
        Node head = new Node(1);
        Node second = new Node(2);
        head.next = second;
        head.random = second;
        second.random = second;

        复制带随机指针的链表 test = new 复制带随机指针的链表();
        test.copyRandomList(head);
    }

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        Node newHead = new Node(head.val);

        Node oldNode = head;
        Node newNode = newHead;

        while (oldNode.next != null) {
            oldNode = oldNode.next;
            Node nextNode = new Node(oldNode.val);
            newNode.next = nextNode;
            newNode = nextNode;
        }

        if (head.random != null) {
            newHead.random = findNode(head, newHead, head.random);
        }

        oldNode = head;
        newNode = newHead;
        while (oldNode.next != null) {
            oldNode = oldNode.next;
            newNode = newNode.next;
            if (oldNode.random != null) {
                newNode.random = findNode(head, newHead, oldNode.random);
            }
        }
        return newHead;

    }

    public Node findNode(Node head, Node newHead, Node target) {
        if (head == target) {
            return newHead;
        }
        while (head.next != null) {
            head = head.next;
            newHead = newHead.next;
            if (head == target) {
                return newHead;
            }
        }
        return null;
    }

}

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
